package cn.demoncat.util.lang.entity.data;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.function.Consumer;
import java.util.function.Predicate;

/**
 * 链表 - 有序列表，链式存储
 * 
 * @author 延晓磊
 *
 * @since 2020年6月27日
 */
public abstract class LinkedList<E> implements Iterable<E>{

	/**
	 * 索引越界异常
	 */
	public static final RuntimeException INDEX_EX =  new RuntimeException("索引越界");
	/**
	 * 链表空异常
	 */
	public static final RuntimeException EMPTY_EX =  new RuntimeException("链表为空");

	// 首节点
	protected LinkedNode<E> first;
	// 尾节点
	protected LinkedNode<E> last;
	// 节点数
	protected int size = 0;
	
	/**
	 * 获取尾部
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	public E last() {
		if (last == null) {
			return null;
		}
		return last.getData();
	}

	/**
	 * 添加到尾部
	 * 
	 * @param e
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	public abstract LinkedList<E> add(E e);

	/**
	 * 获取头部
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	public E first() {
		if (first == null) {
			return null;
		}
		return first.getData();
	}

	/**
	 * 添加到头部
	 * 
	 * @param e
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	public abstract LinkedList<E> first(E e);

	/**
	 * 插入
	 * 
	 * @param index 索引
	 * @param e
	 * 
	 * @throws RuntimeException 索引越界：index < 0 || index > size
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	public abstract void insert(int index, E e);
	
	/**
	 * 获取
	 * 
	 * @param index 索引
	 * @return
	 * 
	 * @throws RuntimeException 索引越界
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	public abstract E get(int index);

	/**
	 * 修改
	 * 
	 * @param index 索引
	 * @param e
	 * 
	 * @return  索引原数据
	 * 
	 * @throws RuntimeException 索引越界
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	public abstract E set(int index, E e);

	/**
	 * 删除
	 * 
	 * @param index 索引
	 * 
	 * @return 索引原数据
	 * 
	 * @throws RuntimeException 索引越界
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	public abstract E del(int index);
	
	/**
	 * 删除
	 * 
	 * @param node	节点
	 * 
	 * @return 节点数据，null表示未找到/节点数据为null
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	public abstract E del(LinkedNode<E> node);
	
	/**
	 * 查询数据，返回节点索引（第一个）
	 * 
	 * @param data	数据，通过equals比较
	 * 
	 * @return 节点索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public int indexOf(E data) {
		return indexOf(data::equals);
	}
	
	/**
	 * 查询数据，返回节点索引（第一个）
	 * 
	 * @param predicate	比较表达式：fn(node.data)
	 * 
	 * @return 节点索引，-1表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public int indexOf(Predicate<E> predicate) {
		if (isEmpty()) {
			return -1;
		}
		// 遍历查找
		int i = 0;
		LinkedNode<E> node = first;
		LinkedNode<E> endTag = endTag();
		// 遍历完成
		do {
			// 比较
			if (predicate.test(node.getData())) {
				return i;
			}
			// 下一个节点
			i++;
			node = node.getNext();
		} while (node != endTag);
		return -1;
	}
	
	/**
	 * 查询节点数据（第一个）
	 * 
	 * @param data	数据，通过equals比较
	 * 
	 * @return 节点数据，null表示未找到/节点数据为null
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public E search(E data) {
		return search(data::equals);
	}
	
	/**
	 * 查询节点数据（第一个）
	 * 
	 * @param predicate	比较表达式：fn(node.data)
	 * 
	 * @return 节点数据，null表示未找到/节点数据为null
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public E search(Predicate<E> predicate) {
		// 查询节点
		LinkedNode<E> node = searchNode(predicate);
		// 返回数据
		return node == null ? null : node.getData();
	}
	
	/**
	 * 查询节点（第一个）
	 * 
	 * @param data	数据，通过equals比较
	 * 
	 * @return 节点，null表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public LinkedNode<E> searchNode(E data) {
		return forEachNode2(node -> data.equals(node.getData()));
	}
	
	/**
	 * 查询节点（第一个）
	 * 
	 * @param predicate	比较表达式：fn(node.data)
	 * 
	 * @return 节点，null表示未找到
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public LinkedNode<E> searchNode(Predicate<E> predicate) {
		return forEachNode2(node -> predicate.test(node.getData()));
	}
	
	/**
	 * 查询数据并删除（第一个）
	 * 
	 * @param data	数据，通过equals比较
	 * 
	 * @return 节点数据，null表示未找到/节点数据为null
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public E remove(E data) {
		return del(searchNode(data));
	}
	
	/**
	 * 查询数据并删除（第一个）
	 * 
	 * @param predicate	比较表达式：fn(node.data)
	 * 
	 * @return 节点数据，null表示未找到/节点数据为null
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public E remove(Predicate<E> predicate) {
		return del(searchNode(predicate));
	}
	
	/**
	 * 查询数据并全部删除
	 * 
	 * @param data	数据，通过equals比较
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public void removeAll(E data) {
		forEachNode(node -> {
			if (data.equals(node.getData())) {
				// 删除
				del(node);
			}
		});
	}
	
	/**
	 * 查询数据并全部删除
	 * 
	 * @param predicate	比较表达式：fn(node.data)
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public void removeAll(Predicate<E> predicate) {
		forEachNode(node -> {
			if (predicate.test(node.getData())) {
				// 删除
				del(node);
			}
		});
	}

	/**
	 * 链表反转
	 * 
	 * @return 新链表
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	public abstract LinkedList<E> reverse();

	/**
	 * 链表长度
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	public int size() {
		return size;
	}
	
	/**
	 * 判断链表是否为空
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月28日
	 */
	public boolean isEmpty() {
		return size == 0;
	}
	
	/**
	 * 判断是否为循环链表
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月28日
	 */
	public abstract boolean isCircle();
	
	/**
	 * 链表结束标记
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public LinkedNode<E> endTag(){
		return isCircle() ? first : null;
	}
	
	/**
	 * 判断是否为链表末尾
	 * 
	 * @param node
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	public boolean isEnd(LinkedNode<E> node) {
		return node == endTag();
	}

	/**
	 * 遍历打印
	 * 
	 * @return
	 *
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public String toString() {
		// 链表为空
		if (size == 0) {
			return "[]";
		}
		// 遍历
		StringBuilder str = new StringBuilder("[");
		LinkedNode<E> node = first;
		LinkedNode<E> endTag = endTag();
		while (true) {
			// 数据
			str.append(node.getData());
			// 下一个节点
			node = node.getNext();
			if (node == endTag) {
				// 遍历完成
				str.append("]");
				break;
			} else {
				str.append(", ");
			}
		}
		return str.toString();
	}
	
	/**
	 * 转换为列表
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月29日
	 */
	public List<E> toList(){
		ArrayList<E> list = new ArrayList<>(size);
		// 遍历
		forEach(list::add);
		return list;
	}
	
	/**
	 * 迭代器（forEach）
	 * 
	 * @return
	 *
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	@Override
	public Iterator<E> iterator() {
		return new Itr();
	}
	
	/**
	 * 遍历节点数据
	 * 
	 * @param fn	消费者：fn(node.data)
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月29日
	 */
	@Override
	public void forEach(Consumer<? super E> fn) {
		// 遍历
		if (!isEmpty()) {
			LinkedNode<E> node = first;
			LinkedNode<E> endTag = endTag();
			// 遍历完成
			do {
				// 节点消费
				fn.accept(node.getData());
				// 下一个节点
				node = node.getNext();
			} while (node != endTag);
		}
	}
	
	/**
	 * 遍历节点数据
	 * 
	 * @param fn	消费者：fn(node.data) = false继续/true返回node.data
	 * 
	 * @return  节点数据
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月29日
	 */
	public E forEach2(Predicate<E> fn) {
		// 遍历
		if (!isEmpty()) {
			LinkedNode<E> node = first;
			LinkedNode<E> endTag = endTag();
			while (true) {
				// 节点消费
				if (fn.test(node.getData())) {
					return node.getData();
				}else {
					// 下一个节点
					node = node.getNext();
					if (node == endTag) {
						// 遍历完成
						break;
					}
				}
			}
		}
		return null;
	}
	
	/**
	 * 遍历节点
	 * 
	 * @param fn	消费者：fn(node)
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月29日
	 */
	public void forEachNode(Consumer<LinkedNode<E>> fn) {
		// 遍历
		if (!isEmpty()) {
			LinkedNode<E> node = first;
			LinkedNode<E> endTag = endTag();
			do {
				// 节点消费
				fn.accept(node);
				// 下一个节点
				node = node.getNext();
			} while (node != endTag);
		}
	}
	
	/**
	 * 遍历节点
	 * 
	 * @param fn	消费者：fn(node) = false继续/true返回node
	 * 
	 * @return  节点
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月29日
	 */
	public LinkedNode<E> forEachNode2(Predicate<LinkedNode<E>> fn) {
		// 遍历
		if (!isEmpty()) {
			LinkedNode<E> node = first;
			LinkedNode<E> endTag = endTag();
			while (true) {
				// 节点消费
				if (fn.test(node)) {
					return node;
				}else {
					// 下一个节点
					node = node.getNext();
					if (node == endTag) {
						// 遍历完成
						break;
					}
				}
			}
		}
		return null;
	}
	
	/**
	 * 迭代器（forEach）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月16日
	 */
	private class Itr implements Iterator<E>{
		
		// 当前元素
		private LinkedNode<E> curr = first;
		// 是否结束
		private boolean end = isEmpty();
		
		@Override
		public boolean hasNext() {
			return !end;
		}

		@Override
		public E next() {
			// 当前数据
			E data = curr.getData();
			// 下一个节点
			curr = curr.getNext();
			if (isEnd(curr)) {
				end = true;
			}
			return data;
		}
	}
	
}
